package dp;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 比特位计数
 * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 */
public class P338 {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        result[0] = 0;
        for (int i = 1; i <= n; i++) {
            int count = result[i - 1];
            int prev = i - 1;
            for (int j = 1; ;) {
                if ((prev & j) == 0) {
                    result[i] = count + 1;
                    break;
                } else {
                    j = j << 1;
                    count -= 1;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] result = new P338().countBits(5);
        List<String> collect = Arrays.stream(result).mapToObj(a -> "" + a).collect(Collectors.toList());
        System.out.println(String.join(",", collect));
    }
}
